"""
Problem 74: https://projecteuler.net/problem=74

The number 145 is well known for the property that the sum of the factorial of its
digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that
link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in
a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest
non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty
non-repeating terms?
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/27
'''

Factorial = [1]
for i in range(1,10):
    Factorial.append(Factorial[i-1]*i)

Sumfd = [0]*1000
Sumfd[0] = 1
def sum_factorial_digits(n:int)->int:
    '''
    >>> print(sum_factorial_digits(145))
    145
    >>> print(sum_factorial_digits(69))
    363600
    '''
    try:
        if Sumfd[n] != 0:
            return Sumfd[n]
    except IndexError:
        pass
    
    ns =str(n)
    if len(ns)>3:
        return sum_factorial_digits(n % 1000) + sum_factorial_digits(n // 1000)

    res = sum(Factorial[d] for d in map(int,ns))
    Sumfd[n] = res
    # print(f'Sumfd[{n}] = {res}')
    return res

PDict = {0:0}
def period(n:int)->int:
    '''
    >>> print(period(145))
    1
    >>> print(period(69))
    5
    >>> print(period(6777))
    60
    '''

    if n in PDict:
        return PDict[n]

    seq = [n]
    while True:
        nextN = sum_factorial_digits(seq[-1])

        if nextN in PDict:
            return len(seq) + PDict[nextN]
            
        if nextN in seq:
            lens = len(seq)
            PDict[n] = lens
            return lens
        else:
            seq.append(nextN)


def solution(limit: int = 1000000, terms:int = 60) -> int:
    res = 0
    for n in range(limit):
        if period(n) == terms:
            # print(n)
            res +=1
    return res

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 4713
